# coding=utf-8
from collections import deque


class Vertex(object):
    """
    图的顶点
    key 顶点的键值
    connected_to 相连顶点字典{key:Vertex}
    distance 顶点之间的距离
    parent 顶点的父顶点
    already_traversal 顶点已经遍历过
    """

    def __init__(self, key):
        self.key = key
        self.connected_to = {}
        self.distance = 0
        self.parent = None
        self.color = "white"
        self.finish = 0

    def __str__(self):
        return str(self.key) + " connected to:" + str([x.key for x in self.connected_to])

    def add_neighbor(self, neighbor, weight=0):
        self.connected_to[neighbor] = weight

    def get_connections(self):
        return self.connected_to.keys()

    def get_key(self):
        return self.key

    def get_weight(self, neighbor):
        return self.connected_to[neighbor]

    def get_distance(self):
        return self.distance

    def set_distance(self, distance):
        self.distance = distance

    def get_parent(self):
        return self.parent

    def set_parent(self, parent):
        self.parent = parent

    def get_color(self):
        return self.color

    def set_color(self, color):
        self.color = color

    def get_finish(self):
        return self.finish

    def set_finish(self, time):
        self.finish = time


class Graph(object):
    def __init__(self):
        self.vertex_dict = {}
        self.num_vertices = 0

    def __contains__(self, key):
        return key in self.vertex_dict

    def __iter__(self):
        return self.vertex_dict.itervalues()

    def get_vertex(self, key):
        if key in self.vertex_dict:
            return self.vertex_dict[key]
        else:
            return None

    def add_vertex(self, key):
        """
        添加一个新的关联地点
        :param key: 地点
        """
        self.vertex_dict[key] = Vertex(key)
        self.num_vertices += 1

    def add_edge(self, f, t, cost=0):
        """
        建立地点之间的关系
        :param f: 地点f
        :param t: 地点t
        :param cost: 权重
        """
        if f not in self.vertex_dict:
            self.add_vertex(f)
        if t not in self.vertex_dict:
            self.add_vertex(t)
        self.vertex_dict[f].add_neighbor(self.vertex_dict[t], cost)

    def get_vertices(self):
        return self.vertex_dict.keys()

    def travers(self, key):
        # type: (object) -> list
        """
        返回路线图
        :param key:终点
        :return: 路线集合
        """
        vertex = self.get_vertex(key)
        parent_vertex = vertex.get_parent()
        route = [key]
        while parent_vertex:
            route.append(parent_vertex.get_key())
            parent_vertex = parent_vertex.get_parent()
        return route


class BFSGraph(Graph):
    def __init__(self):
        super(BFSGraph, self).__init__()
        self.d = deque()

    def bfs(self, start=None):
        """
        以宽度优先算法建立路线关系
        :param start:起点
        """
        if start:
            start_vertex = self.get_vertex(start)
            self.d.append(start_vertex)
            self.bfs_visit()
        else:
            for vertex in self:
                if vertex.get_color() == "white":
                    start_vertex = vertex
                    self.d.append(start_vertex)
                    self.bfs_visit()

    def bfs_visit(self):
        while self.d:
            current_vertex = self.d.popleft()
            for next_vertex in current_vertex.get_connections():
                if next_vertex.get_color() == "white":
                    next_vertex.set_parent(current_vertex)
                    next_vertex.set_distance(current_vertex.get_distance() + 1)
                    self.d.append(next_vertex)
            current_vertex.set_color("black")


class DFSGraph(Graph):
    def __init__(self):
        super(DFSGraph, self).__init__()
        self.time = 0

    def dfs(self, start=None):
        """
        深度优先搜索
        """
        if start:
            start_vertex = self.get_vertex(start)
            self.dfs_visit(start_vertex)
        else:
            for vertex in self:
                if vertex.get_color() == "white":
                    self.dfs_visit(vertex)

    def dfs_visit(self, start_vertex):
        start_vertex.set_color("gray")
        self.time += 1
        start_vertex.set_distance(self.time)
        for next_vertex in start_vertex.get_connections():
            if next_vertex.get_color() == "white":
                next_vertex.set_parent(start_vertex)
        start_vertex.set_color("black")
        self.time += 1
        start_vertex.set_finish(self.time)


if __name__ == '__main__':
    pass
